Faktorizáció
A faktorizáció azt a folyamatot jelöli, amely során egy objektumot (például egész számok faktorizációja, polinomok faktorizációja, mátrixok faktorizációja) nála valamilyen szempontból „kisebb” elemek szorzatára bontunk. Például a 15 természetes szám faktorizációja a természetes számok feletti prímelemek szorzatára: 3 * 5, míg az x2 − 4 polinom faktorizációja az egész számok fölötti polinomgyűrűben: (x − 2)(x + 2).
A faktorizálás célja az, hogy valamit nála kisebb „elemi építőelemek” szorzatára felbontsunk. Például egész számok esetében prímszámokra, polinomok esetén irreducibilis polinomokra.
A polinomfaktorizáció ellentéte a kibontás vagy beszorzás, amikor az azt alkotó polinomok összeszorzását elvégezzük.
A nagy számok prímfelbontása nehéz probléma, így ezt a tulajdonságot alkalmazzák bizonyos titkosításokban, például az RSA-ban.
Egész számok[szerkesztés]
A számelmélet alaptételének megfelelően, minden 1-nél nagyobb egész szám egyértelműen felírható prímek szorzataként. A prímfelbontási algoritmus az 1-nél nagyobb egész számnak megadja a prímosztóit.[1] Nagy számokra nem ismert hatékony prímfelbontó algoritmus.
Polinomok[szerkesztés]
Másodfokú polinomok[szerkesztés]
Bármely másodfokú komplex együtthatós polinom felírható elsőfokú komplex együtthatós polinomok és egy konstans szorzatára, a következőképpen:
ahol és a polinom két gyöke. A másodfokú polinom gyökeit a másodfokú egyenlet megoldóképletével találhatjuk meg.
Az egész számok fölött faktorizálható másodfokú polinomok[szerkesztés]
Bizonyos másodfokú polinomok felbonthatóak az egész számok teste fölötti elsőfokú polinomok és egy konstans szorzatára.
Teljes négyzetek[szerkesztés]
Teljes négyzetnek azokat a polinomokat nevezzük, amelyek felírhatóak egy elsőfokú polinom négyzeteként. Ha egy polinom teljes négyzet, akkor a következőképpen faktorizálható:
vagy
Négyzetek összege, különbsége[szerkesztés]
Egy másik nagyon hasznos azonosság a négyzetek különbsége:
Ha a négyzetek nem kivonva, hanem összeadva vannak, akkor helyett helyettesítsünk -t a fenti formulába, és így kaphatjuk a következő azonosságot:
faktorizációja például .
Egyéb polinomok faktorizációja[szerkesztés]
Két köb összege/különbsége[szerkesztés]
Egy ismert formula köbök összegére a következő:
a különbségükre pedig:
Két negyedik hatvány különbsége[szerkesztés]
Szintén ismert formula két negyedik hatvány különbségének kifejezésére:
Ez a formula levezethető a két négyzet különbségére vonatkozó formulából az a4-t és a b4-t a2 és b2 négyzeteként kezelve.
Két ötödik hatvány összege/különbsége[szerkesztés]
Szintén ismertek a következő formulák:
a különbségre pedig:
(További faktorizáció is lehetséges, de ekkor az együtthatók megszűnnek egészeknek lenni.)
Két n-edik hatvány összege/különbsége[szerkesztés]
A fenti különbségre vonatkozó formulákat ki lehet terjeszteni általános hatványra is a geometriai sorozat első n elemének összegére való formulával. Mivel
így (x − 1)-el szorozva az egyenlet mindkét oldalát, megkapjuk az általános formula egy formáját. Az általánosan elterjedt formához helyettesítsünk x helyett a/b-t, és mindkét oldalt szorozzuk meg bn-nel. Így kapjuk, hogy:
Az ehhez tartozó összegre vonatkozó képlet attól függ, hogy n páros vagy páratlan. Ha n páratlan, akkor b-t −b-re cserélve a fenti formulában, azt kapjuk, hogy:
Ha n páros, akkor két eset lehetséges:
- Ha n 2 hatványa, akkor
- felbonthatatlan a valós számok körében.
- Különben legyen
- , ahol m páratlan.
- Ekkor a kifejezés a következő alakot ölti:
- Így az általános formula:
Sophie Germain-féle azonosság[szerkesztés]
A Sophie Germain-féle azonosság[2] alapján
A levezetése a következő:
Egyéb faktorizációs formulák[szerkesztés]
Mátrixok[szerkesztés]
Fordítás[szerkesztés]
Ez a szócikk részben vagy egészben a Factorization című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Források[szerkesztés]
- ↑ An Introduction to the Theory of Numbers, 5th, Oxford Science Publications (1980). ISBN 978-0198531715
- ↑ Sophie Germain Identity (angol nyelven). Art of Problem Solving Wiki. [2018. augusztus 16-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. augusztus 16.)